package com.chapter3.search;

import java.util.Iterator;

/** 
 * @ClassName: BinarySearchST 
 * @Description: 二分法查找优化的符号表
 * @author minjun minjun@bw30.com
 * @date 2015-2-18 下午1:06:55 
 *  
 */
public class BinarySearchST<K extends Comparable<K>,V> extends AbstractST<K, V>{
	
	private K[] keys;
	
	private V[] values;
	
	private int capacity=1<<16;
	
	@SuppressWarnings("unchecked")
	public BinarySearchST() {
		keys= (K[]) new Comparable[capacity];
		values=(V[]) new Object[capacity];
	}

	/**
	 * 虽然get的操作的时间复杂度变成了lgN，但是put方法的时间复杂度还是2N，依然有值得改进的地方
	 */
	@Override
	public void put(K k, V v) {
		//获取比k小的Key数量（k的位置）
		int i=rank(k);
		if(i<size&&k.compareTo(keys[i])==0){
			values[i]=v;
			return;
		}
		for(int j=size;j>i;j--){
			keys[j]=keys[j-1];
			values[j]=values[j-1];
		}
		keys[i]=k;
		values[i]=v;
		size++;
		
	}

	@Override
	public V get(K k) {
		if(isEmpty()) 
			return null;
		//获取比k小的key数量(k的位置)
		int i=rank(k);
		//如果拿到的值在指定范围内，那么直接获取该key所对应的value
		if(i<size&&k.compareTo(keys[i])==0)
			return values[i];
		return null;
	}
	
	/**
	 * 
	* @Title: rank 
	* @Description: 获取比该key小的key数量 
	* @param @param k
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws
	 */
	private int rank(K k){
		//通过二分法查找寻找所在位置
		int i=0;
		int j=size-1;
		while(i<=j){
			int mid=(i+j)/2;
			int result=keys[mid].compareTo(k);
			if(result>0){
				//key比中间值要小
				j=mid-1;
			}else if(result<0){
				//key比中间值要大
				i=mid+1;
			}else{
				//找到了指定值
				return mid;
			}
		}
		//即时不在里面，也要返回该Key所应该存在的位置
		return i;
	}

	@Override
	public void delete(K k) {
		
	}

	@Override
	public boolean contains(K k) {
		if(isEmpty()) 
			return false;
		int i=rank(k);
		return i<size&&k.compareTo(keys[i])==0;
	}

	@Override
	public Iterator<K> iterator() {
		return new MyIterator();
	}

	private class MyIterator implements Iterator<K>{
		
		private int index;

		@Override
		public boolean hasNext() {
			return keys[index]!=null;
		}

		@Override
		public K next() {
			if(hasNext()){
				return keys[index++];
			}
			throw new RuntimeException("没有元素了");
		}

		@Override
		public void remove() {
			
		}
		
	} 
}
